The present invention claims priority from Japanese Patent Applications No. 10-165406 filed Jun. 12, 1998, No. 11-013273 filed Jan. 21, 1999 and 11-045406 filed Feb. 23, 1999, the contents of which are incorporated herein by reference.
1. Field of the Invention
The present invention relates to networks defined in IEEE 1394 (IEEE Std 1394-1995: IEEE Standard for High Performance Serial Bus, IEEE P1394.a, and others). It relates in particular to techniques for path restoration and avoidance of incorrect connection of links.
2. Description of Related Art
In a network based on IEEE 1394, the nodes are connected in a tree topology (which combines daisy-chains and branches). To communicate, the nodes therefore have to identify the tree topology and determine the connection relations among the nodes.
This tree identification process will now be described. At power-up and when a node is added to a bus, bus initialization takes place to determine the connection relations among the nodes. This involves sending a bus reset signal to all nodes. This signal results in all information relating to the configuration of node connections being cleared. At bus initialization, the only information that each node has is whether it is a branch node connected to two or more other nodes, or a leaf node connected to just one other node, or whether it is not connected to any other node at all.
FIG. 20 and FIG. 21 give examples of how nodes identify a tree. When nodes A, B, C, D and E comprising a network are to start operating, a bus reset signal is sent to each node. The bus reset signal is a control signal for bus initialization. In these examples, if the nodes are connected by links AB, AC, BD and BE and a change occurs in the network configuration, each node detects the change and respectively sends a bus reset signal.
For example, if link AB is installed to connect node A and node B, nodes A and B each detect that link AB has been connected to it, and send a bus reset signal. If link AC is then installed to connect node A and node C, nodes A and C each detect that link AC has been connected to it, and send a bus reset signal.
Similarly, if link BD is installed to connect node B and node D, nodes B and D each detect that link BD has been connected to it, and send a bus reset signal. If link BE is installed to connect node B and node E, nodes B and E each detect that link BE has been connected to it, and send a bus reset signal.
Thus every time a new link is installed and a node is added, a bus reset signal is sent from the nodes which have detected this change. Because these bus reset signals reach each node, bus initialization takes place throughout the network. Conversely, every time an existing link is removed and the number of nodes decreased, a bus reset signal is sent from the nodes which have detected this change. Again, because these bus reset signals reach each node, bus initialization takes place throughout the network.
This process will be described in greater detail with reference to FIG. 20, where it will be seen that the first step is for signals notifying parent nodes from child nodes (parent_notify signals) are sent from all leaf nodes C, D and E to branch nodes A and B. The nodes which receive a parent_notify signal recognize the node which has sent this parent_notify signal as a child node, and send back a signal indicative of parent-to-child notification (a child_notify signal). This results in the parent-child relations among the nodes being determined.
After a fixed time has elapsed, a second step takes place. As shown in FIG. 21, this involves node A and node B each recognizing that despite having a port whereby link AB is connected, the node has received neither a parent_notify signal nor a child_notify signal, whereupon nodes A and B send a parent_notify signal to each other. When nodes A and B recognize that they have received a parent_notify signal, they each set an independent fixed time. A parent_notify signal is then sent from the node at which the fixed time first elapses. In the example of FIG. 21, it is assumed that node B has re-sent a parent_notify signal to node A. Since it is node A which has received this re-sent parent_notify signal, it constitutes the parent and sends back a child_notify signal to node B.
Thus each node receives a parent_notify signal or a child_notify signal, and thereby successively ascertains whether it is a leaf node or a branch node. Tree identification in the network takes place in this way.
FIG. 22 shows the connection relations of nodes among which a loop has been formed. If a loop forms among nodes A, B and C as shown in FIG. 22, normal connections do not hold among these nodes. That is to say, each such node has two ports at which neither a parent_notify signal nor a child_notify signal is received. Such nodes are unable to exchange parent_notify signals with the adjacent nodes to which they are mutually connected in the loop, and are unable to recognize their connection relations. If this state of affairs persists, a limited time (config_timeout) elapses and the bus is automatically reset.
This is because, in the second step described above, if a node has two ports at which neither a parent_notify signal nor a child_notify signal is received despite the relevant links being connected, that node comes under the application of a rule not to send a parent_notify signal.
The reason for this rule is that the procedure of sending parent_notify signals in the aforementioned second step has the purpose of enabling a higher-level node to be recognized. However, with a tree structure, a given node always has just one higher-level node and cannot have two. It follows that if a node has two ports at which neither a parent_notify signal nor a child_notify signal has been received despite the relevant links being connected, it judges that it is possible that there is a lower-level node which has not yet sent a parent_notify signal to it, with the result that it does not send a parent_notify signal.
Consequently, the tree identification procedure is repeated indefinitely and cannot be completed. As a result, since the initialization process cannot be completed, communication becomes impossible.
We now look at another problem. FIG. 23 shows the connection relations of nodes among which a fault has occurred. If link AB between nodes A and B is disconnected as shown in FIG. 23, then as long as the network comprising nodes A and C, and the network constituted by nodes B, D and E remain separate, these networks will undergo independent bus initialization. The result is that the two networks operate independently and cannot intercommunicate.
However, given this scenario, if link BC has been present between node B and node C as shown by the broken lines in FIG. 23, a route which bypasses the fault can be formed and normal communication performed. However, as described with reference to FIG. 22, because link BC between node B and node C would result in a loop being formed among nodes A, B and C, it cannot be provided in advance. Thus in an IEEE 1394 based network the advance provision of redundant links for path restoration in the event of link faults is problematic.
In the light of the foregoing considerations, it is an object of the present invention to provide a network and a node device whereby communication is possible even when nodes are connected in a loop. It is another object of the present invention to provide a high-reliability IEEE 1394 based network and node device which, when a fault has occurred in a link, is capable of rapidly forming a route which bypasses the fault.
It is a particular feature of the present invention that it provides switching means for connecting and disconnecting a link between nodes, so that when an IEEE 1394 based network has a redundant link which forms a loop among nodesxe2x80x94this loop preventing normal connection relations being maintainedxe2x80x94the connection relations can be made normal by controlling this switching means.
Controlling the switching means also achieves rapid recovery from a fault which has occurred in a link between nodes, by utilizing the aforementioned loop to form a route that bypasses the fault.
According to a first aspect, the present invention is a network comprising a plurality of nodes and links connecting these nodes, wherein each node is provided with means for exchanging, with other nodes to which it is connected and by way of the aforementioned links, information confirming connection relations.
A particular feature of this aspect of the invention is that a node is provided with switching means which, if the node has two or more links for which the connection relations have not been confirmed after the elapse of sufficient time for exchanging the confirmation information, disconnects at least one of these links.
The switching means preferably comprises means which, when the aforementioned connection relation confirmation procedure is performed repeatedly, disconnects at least one of the links, other than a link which was previously disconnected.
A network according to the first aspect described above can also comprise: means for selecting one of the links for which the connection relations have not been confirmed after the elapse of sufficient time (Ti) for exchanging the confirmation information; means which employs the aforementioned switching means to disconnect the link selected by this selection means, and which causes there to be sent, from the node connected to the other side of this selected link, a signal which starts the exchange of information confirming the connection relations; reception detection means which detects whether or not it receives the signal which starts the exchange of information confirming the connection relations within the sufficient time (Ti) for exchanging the confirmation information; and loop detection means for detecting, in accordance with the detection results of this reception detection means, links which form a loop. Alternatively, a network according to the first aspect can comprise: means for selecting; after the elapse of sufficient time (Ti) for exchanging the confirmation information, one of the links for which the connection relations have not been confirmed; means which sends, to the link selected by this selection means, a signal which starts the exchange of information confirming the connection relations; reception detection means which detects whether or not it receives the signal which starts the exchange of information confirming the connection relations within the sufficient time (Ti) for exchanging the confirmation information; and loop detection means for detecting, in accordance with the detection results of this reception detection means, links which form a loop.
The loop detection means can alternatively comprise means which, when the reception detection means has received; via a link other than the link selected by the selection means, a signal starting the exchange of information confirming the connection relations, decides that the link selected by the selection means is a link which forms a loop. Alternatively, the loop detection means can comprise means which, when the reception detection means has received, via a link other than the link selected by the selection means, a signal starting the exchange of information confirming the connection relations, decides that this other link is a link which forms a loop.
That is to say, when there are a plurality of links for which the parent-child relation is unknown, the node that was connected to the other side of one of these links is made to send a signal which starts the exchange of information confirming the connection relations. Alternatively, the local node itself sends to this node a signal starting the exchange of information confirming the connection relations. If the signal from said node starting the exchange of information confirming the connection relations cannot be received via a link other than the link in question, it can be decided that the link in question has formed a loop, or conversely, that a link other than the link in question has formed a loop. Consequently, a normal network configuration can be formed by disconnecting either the link in question or the other link, and then making another attempt to confirm the parent-child relation. If the procedure for confirming the connection relations is performed repeatedly, the link disconnected at a given stage should not be a link which has previously been disconnected.
If the aforementioned connection relations are based on a tree topology in which the branch nodes are predetermined, the aforementioned selection means can comprise means for preferentially selecting from among links other than those connected to branch nodes. This enables a network configuration with fewer series-connected nodes to be formed.
If the aforementioned switching means is provided in each of a plurality of nodes in the same network, there is provided means which sets the aforementioned sufficient time (Ti) to a mutually different time for each of the plurality of nodes.
If the aforementioned connection relations are based on a tree topology in which the branch nodes are predetermined, the aforementioned setting means can comprise means which sets a longer sufficient time (Ti) for nodes nearer the root nodes.
That is to say, when there are a plurality of nodes with switching means in a single network, their sufficient times (Ti) are preferably set to mutually different times. This ensures that the procedure for confirming connection relations is performed in a regular order, i.e., after one node has confirmed connection relations, the next node starts to confirm connection relations. This prevents confusion occurring in the task of confirming connection relations among a plurality of nodes in the same network. If the connection relations are based on a tree topology, setting a longer sufficient time (Ti) the nearer a node is to a root node enables the confirmation of connection relations to start with nodes corresponding to branches and to proceed to nodes nearer the root. This ensures efficient confirmation of connection relations.
The switching means can comprise means for physically disconnecting a link, or it can comprise means for logically disconnecting a link. The means which disconnects logically preferably comprises means which disables the interface to which the link to be disconnected from the local node is connected.
Thus, because normal connection relations can be maintained even if a loop has been formed among nodes, a redundant link can be provided in advance in a network without concern that a loop may be formed, the redundant link serving as an alternative route in the event of a fault occurring. It follows that a high-reliability IEEE 1394 based network using branch/leaf (or parent/child) connection relations can be realized.
According to a second aspect, the present invention is a node device disposed at a node of a network according to this invention.